home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / 1989 / 09 / nevin.lst < prev    next >
File List  |  1989-07-27  |  24KB  |  664 lines
  1.  
  2. _AUTOROUTING WITH THE A* ALGORITHM_
  3. by Randy Nevin
  4.  
  5. [LISTING ONE]
  6.  
  7. /*
  8. ** printed circuit board autorouter, Copyright (C) Randy Nevin 1989.
  9. ** you may give this software to anyone, make as many copies as you
  10. ** like, and post it on public computer bulletin boards and file
  11. ** servers. you may not sell it or charge any fee for distribution
  12. ** (except for media and postage), remove this comment or the
  13. ** copyright notice from the code, or claim that you wrote this code
  14. ** or anything derived from it.
  15. ** the author's address is: Randy Nevin, 1731 211th PL NE, Redmond,
  16. ** WA 98053. this code is available directly from the author; just
  17. ** send a floppy and a self-addressed floppy mailer with sufficient
  18. ** postage. however, you should first attempt to get a copy of this
  19. ** software package from the Dr. Dobb's Journal BBS.
  20. */
  21. /* the low-order bit indicates a hole */
  22. #define HOLE         0x00000001L /* a conducting hole */
  23. /* traces radiating outward from a hole to a side or corner */
  24. #define HOLE_NORTH     0x00000002L /* upward             */
  25. #define HOLE_NORTHEAST     0x00000004L /* upward and right   */
  26. #define HOLE_EAST     0x00000008L /* to the right       */
  27. #define HOLE_SOUTHEAST     0x00000010L /* downward and right */
  28. #define HOLE_SOUTH     0x00000020L /* downward           */
  29. #define HOLE_SOUTHWEST     0x00000040L /* downward and left  */
  30. #define HOLE_WEST     0x00000080L /* to the left        */
  31. #define HOLE_NORTHWEST     0x00000100L /* upward and left    */
  32.  
  33. /* straight lines through the center */
  34. #define LINE_HORIZONTAL     0x00000002L /* left-to-right line */
  35. #define LINE_VERTICAL     0x00000004L /* top-to-bottom line */
  36.  
  37. /* lines cutting across a corner, connecting adjacent sides */
  38. #define CORNER_NORTHEAST 0x00000008L /* upper right corner */
  39. #define CORNER_SOUTHEAST 0x00000010L /* lower right corner */
  40. #define CORNER_SOUTHWEST 0x00000020L /* lower left corner  */
  41. #define CORNER_NORTHWEST 0x00000040L /* upper left corner  */
  42.  
  43. /* diagonal lines through the center */
  44. #define DIAG_NEtoSW     0x00000080L /* northeast to southwest */
  45. #define DIAG_SEtoNW     0x00000100L /* southeast to northwest */
  46.  
  47. /* 135 degree angle side-to-far-corner lines */
  48. #define BENT_NtoSE     0x00000200L /* north to southeast */
  49. #define BENT_NtoSW     0x00000400L /* north to southwest */
  50. #define BENT_EtoSW     0x00000800L /* east to southwest  */
  51. #define BENT_EtoNW     0x00001000L /* east to northwest  */
  52. #define BENT_StoNW     0x00002000L /* south to northwest */
  53. #define BENT_StoNE     0x00004000L /* south to northeast */
  54. #define BENT_WtoNE     0x00008000L /* west to northeast  */
  55. #define BENT_WtoSE     0x00010000L /* west to southeast  */
  56.  
  57. /* 90 degree corner-to-adjacent-corner lines */
  58. #define ANGLE_NEtoSE     0x00020000L /* northeast to southeast */
  59. #define ANGLE_SEtoSW     0x00040000L /* southeast to southwest */
  60. #define ANGLE_SWtoNW     0x00080000L /* southwest to northwest */
  61. #define ANGLE_NWtoNE     0x00100000L /* northwest to northeast */
  62.  
  63. /* 45 degree angle side-to-near-corner lines */
  64. #define SHARP_NtoNE     0x00200000L /* north to northeast */
  65. #define SHARP_EtoNE     0x00400000L /* east to northeast  */
  66. #define SHARP_EtoSE     0x00800000L /* east to southeast  */
  67. #define SHARP_StoSE     0x01000000L /* south to southeast */
  68. #define SHARP_StoSW     0x02000000L /* south to southwest */
  69. #define SHARP_WtoSW     0x04000000L /* west to southwest  */
  70. #define SHARP_WtoNW     0x08000000L /* west to northwest  */
  71. #define SHARP_NtoNW     0x10000000L /* north to northwest */
  72.  
  73. /* directions the cell can be reached from (point to previous cell) */
  74. #define FROM_NORTH    1
  75. #define FROM_NORTHEAST    2
  76. #define FROM_EAST    3
  77. #define FROM_SOUTHEAST    4
  78. #define FROM_SOUTH    5
  79. #define FROM_SOUTHWEST    6
  80. #define FROM_WEST    7
  81. #define FROM_NORTHWEST    8
  82. #define FROM_OTHERSIDE    9
  83.  
  84. #define    TOP    0
  85. #define BOTTOM    1
  86. #define EMPTY    0
  87. #define ILLEGAL    -1
  88.  
  89. /* visit neighboring cells in this order
  90. ** (where [9] is on the other side):
  91. **    +---+---+---+
  92. **    | 1 | 2 | 3 |
  93. **    +---+---+---+
  94. **    | 4 |[9]| 5 |
  95. **    +---+---+---+
  96. **    | 6 | 7 | 8 |
  97. **    +---+---+---+
  98. */
  99.  
  100. static int delta[8][2] = { /* for visiting neighbors on the same side */
  101.      {  1, -1 }, /* northwest    */
  102.      {  1,  0 }, /* north        */
  103.      {  1,  1 }, /* northeast    */
  104.      {  0, -1 }, /* west        */
  105.      {  0,  1 }, /* east        */
  106.      { -1, -1 }, /* southwest    */
  107.      { -1,  0 }, /* south        */
  108.      { -1,  1 }  /* southeast    */
  109.     };
  110.  
  111. static int ndir[8] = { /* for building paths back to source */
  112.      FROM_SOUTHEAST, FROM_SOUTH, FROM_SOUTHWEST,
  113.      FROM_EAST,                  FROM_WEST,
  114.      FROM_NORTHEAST, FROM_NORTH, FROM_NORTHWEST
  115.     };
  116.  
  117. /* blocking masks for neighboring cells */
  118. #define BLOCK_NORTHEAST    ( DIAG_NEtoSW | BENT_StoNE | BENT_WtoNE \
  119.             | ANGLE_NEtoSE | ANGLE_NWtoNE \
  120.             | SHARP_NtoNE | SHARP_EtoNE )
  121. #define BLOCK_SOUTHEAST    ( DIAG_SEtoNW | BENT_NtoSE | BENT_WtoSE \
  122.             | ANGLE_NEtoSE | ANGLE_SEtoSW \
  123.             | SHARP_EtoSE | SHARP_StoSE )
  124. #define BLOCK_SOUTHWEST    ( DIAG_NEtoSW | BENT_NtoSW | BENT_EtoSW \
  125.             | ANGLE_SEtoSW | ANGLE_SWtoNW \
  126.             | SHARP_StoSW | SHARP_WtoSW )
  127. #define BLOCK_NORTHWEST    ( DIAG_SEtoNW | BENT_EtoNW | BENT_StoNW \
  128.             | ANGLE_SWtoNW | ANGLE_NWtoNE \
  129.             | SHARP_WtoNW | SHARP_NtoNW )
  130. struct block {
  131.     int r1, c1;  long b1, h1;
  132.     int r2, c2;  long b2, h2;
  133.     };
  134. static struct block blocking[8] = { /* blocking masks */
  135.      {  0, -1, BLOCK_NORTHEAST, HOLE_NORTHEAST,
  136.         1,  0, BLOCK_SOUTHWEST, HOLE_SOUTHWEST },
  137.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  138.      {  1,  0, BLOCK_SOUTHEAST, HOLE_SOUTHEAST,
  139.         0,  1, BLOCK_NORTHWEST, HOLE_NORTHWEST },
  140.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  141.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  142.      {  0, -1, BLOCK_SOUTHEAST, HOLE_SOUTHEAST,
  143.        -1,  0, BLOCK_NORTHWEST, HOLE_NORTHWEST },
  144.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  145.      { -1,  0, BLOCK_NORTHEAST, HOLE_NORTHEAST,
  146.         0,  1, BLOCK_SOUTHWEST, HOLE_SOUTHWEST }
  147.     };
  148. static int selfok[5][8] = { /* mask for self-blocking corner effects */
  149.      { 1, 1, 1, 1, 1, 1, 1, 1 },
  150.      { 0, 0, 0, 0, 1, 0, 1, 0 },
  151.      { 0, 0, 0, 1, 0, 0, 1, 0 },
  152.      { 0, 1, 0, 0, 1, 0, 0, 0 },
  153.      { 0, 1, 0, 1, 0, 0, 0, 0 }
  154.     };
  155. static long newmask[5][8] = { /* patterns to mask in neighbor cells */
  156.      { 0, 0, 0, 0, 0, 0, 0, 0 },
  157.      { 0, 0, 0, 0, CORNER_NORTHEAST | CORNER_SOUTHEAST, 0,
  158.        CORNER_SOUTHEAST | CORNER_SOUTHWEST, 0 },
  159.      { 0, 0, 0, CORNER_SOUTHWEST | CORNER_NORTHWEST, 0, 0,
  160.        CORNER_SOUTHEAST | CORNER_SOUTHWEST, 0 },
  161.      { 0, CORNER_NORTHEAST | CORNER_NORTHWEST, 0, 0,
  162.        CORNER_NORTHEAST | CORNER_SOUTHEAST, 0, 0, 0 },
  163.      { 0, CORNER_NORTHEAST | CORNER_NORTHWEST, 0,
  164.        CORNER_SOUTHWEST | CORNER_NORTHWEST, 0, 0, 0, 0 }
  165.     };
  166. /* board dimensions */
  167. extern int Nrows;
  168. extern int Ncols;
  169.  
  170. void Solve () { /* route all traces */
  171.     int r1, c1, r2, c2, r, c, s, d, a, nr, nc, skip;
  172.     register int i;
  173.     char far *n1;
  174.     char far *n2;
  175.     long curcell, newcell, buddy;
  176.     int newdist, olddir, success, self;
  177.  
  178.     /* go until no more work to do */
  179.     for (GetWork( &r1, &c1, &n1, &r2, &c2, &n2 ); r1 != ILLEGAL;
  180.             GetWork( &r1, &c1, &n1, &r2, &c2, &n2 )) {
  181.         if (r1 == r2 && c1 == c2) /* already routed */
  182.             continue;
  183.         success = 0;
  184.         InitQueue(); /* initialize the search queue */
  185.         /* get rough estimate of trace distance */
  186.         a = GetApxDist( r1, c1, r2, c2 );
  187.         SetQueue( r1, c1, TOP, 0, a, r2, c2 );
  188.         SetQueue( r1, c1, BOTTOM, 0, a, r2, c2 );
  189.         /* search until success or we exhaust all possibilities */
  190.         for (GetQueue( &r, &c, &s, &d, &a ); r != ILLEGAL;
  191.             GetQueue( &r, &c, &s, &d, &a )) {
  192.             if (r == r2 && c == c2) { /* success! */
  193.                 /* lay traces */
  194.                 Retrace( r1, c1, r2, c2, s );
  195.                 success++;
  196.                 break;
  197.                 }
  198.             curcell = GetCell( r, c, s );
  199.             if (curcell & CORNER_NORTHWEST)
  200.                 self = 1;
  201.             else if (curcell & CORNER_NORTHEAST)
  202.                 self = 2;
  203.             else if (curcell & CORNER_SOUTHWEST)
  204.                 self = 3;
  205.             else if (curcell & CORNER_SOUTHEAST)
  206.                 self = 4;
  207.             else
  208.                 self = 0;
  209.             /* consider neighbors */
  210.             for (i = 0; i < 8; i++) {
  211.                 /* check self-block */
  212.                 if (!selfok[self][i])
  213.                     continue;
  214.                 if ((nr = r+delta[i][0]) < 0
  215.                     || nr >= Nrows
  216.                     || (nc = c+delta[i][1]) < 0
  217.                     || nc >= Ncols)
  218.                     /* off the edge */
  219.                     continue;
  220.                 newcell = GetCell( nr, nc, s );
  221.                 /* check for non-target hole */
  222.                 if (newcell & HOLE) {
  223.                     if (nr != r2 || nc != c2)
  224.                         continue;
  225.                     }
  226.                 else {
  227.                     newcell &= ~(newmask[self][i]);
  228.                     /* check for traces */
  229.                     if (newcell)
  230.                         continue;
  231.                     }
  232.                 /* check blocking on corner neighbors */
  233.                 if (delta[i][0] && delta[i][1]) {
  234.                     /* check first buddy */
  235.                     buddy = GetCell( r+blocking[i].r1,
  236.                         c+blocking[i].c1, s );
  237.                     if (buddy & HOLE) {
  238.                         if (buddy & (blocking[i].h1))
  239.                             continue;
  240.                         }
  241.                     else if (buddy & (blocking[i].b1))
  242.                         continue;
  243.                     /* check second buddy */
  244.                     buddy = GetCell( r+blocking[i].r2,
  245.                         c+blocking[i].c2, s );
  246.                     if (buddy & HOLE) {
  247.                         if (buddy & (blocking[i].h2))
  248.                             continue;
  249.                         }
  250.                     else if (buddy & (blocking[i].b2))
  251.                         continue;
  252.                     }
  253.                 olddir = GetDir( r, c, s );
  254.                 newdist = d+CalcDist( ndir[i], olddir,
  255.                     (olddir == FROM_OTHERSIDE)
  256.                     ? GetDir( r, c, 1-s ) : 0 );
  257.                 /* if not visited yet, add it to queue */
  258.                 if (!GetDir( nr, nc, s )) {
  259.                     SetDir( nr, nc, s, ndir[i] );
  260.                     SetDist( nr, nc, s, newdist );
  261.                     SetQueue( nr, nc, s, newdist,
  262.                         GetApxDist( nr, nc, r2, c2 ),
  263.                         r2, c2 );
  264.                     }
  265.                 /* we might have found a better path */
  266.                 else if (newdist < GetDist( nr, nc, s )) {
  267.                     SetDir( nr, nc, s, ndir[i] );
  268.                     SetDist( nr, nc, s, newdist );
  269.                     ReSetQueue( nr, nc, s, newdist,
  270.                         GetApxDist( nr, nc, r2, c2 ),
  271.                         r2, c2 );
  272.                     }
  273.                 }
  274.             /* consider other side of board */
  275.             /* check for holes or traces on other side */
  276.             if (newcell = GetCell( r, c, 1-s ))
  277.                 continue;
  278.             skip = 0;
  279.             /* check for nearby holes */
  280.             for (i = 0; i < 8; i++) {
  281.                 if ((nr = r+delta[i][0]) < 0
  282.                     || nr >= Nrows
  283.                     || (nc = c+delta[i][1]) < 0
  284.                     || nc >= Ncols)
  285.                     /* off the edge */
  286.                     continue;
  287.                 if (GetCell( nr, nc, s ) & HOLE) {
  288.                     /* neighboring hole */
  289.                     skip = 1;
  290.                     break;
  291.                     }
  292.                 }
  293.             if (skip) /* neighboring hole? */
  294.                 continue; /* yes, can't drill one here */
  295.             olddir = GetDir( r, c, s );
  296.             newdist = d+CalcDist( FROM_OTHERSIDE, olddir,
  297.                 (olddir == FROM_OTHERSIDE)
  298.                 ? GetDir( r, c, 1-s ) : 0 );
  299.             /* if not visited yet, add it to queue */
  300.             if (!GetDir( r, c, 1-s )) {
  301.                 SetDir( r, c, 1-s, FROM_OTHERSIDE );
  302.                 SetDist( r, c, 1-s, newdist );
  303.                 SetQueue( r, c, 1-s, newdist,
  304.                     a, r2, c2 );
  305.                 }
  306.             /* we might have found a better path */
  307.             else if (newdist < GetDist( r, c, 1-s )) {
  308.                 SetDir( r, c, 1-s, FROM_OTHERSIDE );
  309.                 SetDist( r, c, 1-s, newdist );
  310.                 ReSetQueue( r, c, 1-s, newdist,
  311.                     a, r2, c2 );
  312.                 }
  313.             }
  314.         if (!success)
  315.             printf( "\t*!* UNSUCCESSFUL *!*\n" );
  316.         /* clear direction flags */
  317.         for (r = 0; r < Nrows; r++) {
  318.             for (c = 0; c < Ncols; c++) {
  319.                 SetDir( r, c, TOP, EMPTY );
  320.                 SetDir( r, c, BOTTOM, EMPTY );
  321.                 }
  322.             }
  323.         }
  324.     }
  325. /* this table drives the retracing phase */
  326. static long bit[8][9] = { /* OT=Otherside */
  327.      /* N, NE, E, SE, S, SW, W, NW, OT */
  328. /* N */  { LINE_VERTICAL, BENT_StoNE, CORNER_SOUTHEAST, SHARP_StoSE,
  329.        0, SHARP_StoSW, CORNER_SOUTHWEST, BENT_StoNW,
  330.        (HOLE | HOLE_SOUTH) },
  331. /* NE */ { BENT_NtoSW, DIAG_NEtoSW, BENT_EtoSW, ANGLE_SEtoSW,
  332.        SHARP_StoSW, 0, SHARP_WtoSW, ANGLE_SWtoNW,
  333.        (HOLE | HOLE_SOUTHWEST) },
  334. /* E */  { CORNER_NORTHWEST, BENT_WtoNE, LINE_HORIZONTAL, BENT_WtoSE,
  335.        CORNER_SOUTHWEST, SHARP_WtoSW, 0, SHARP_WtoNW,
  336.        (HOLE | HOLE_WEST) },
  337. /* SE */ { SHARP_NtoNW, ANGLE_NWtoNE, BENT_EtoNW, DIAG_SEtoNW,
  338.        BENT_StoNW, ANGLE_SWtoNW, SHARP_WtoNW, 0,
  339.        (HOLE | HOLE_NORTHWEST) },
  340. /* S */  { 0, SHARP_NtoNE, CORNER_NORTHEAST, BENT_NtoSE,
  341.        LINE_VERTICAL, BENT_NtoSW, CORNER_NORTHWEST, SHARP_NtoNW,
  342.        (HOLE | HOLE_NORTH) },
  343. /* SW */ { SHARP_NtoNE, 0, SHARP_EtoNE, ANGLE_NEtoSE, BENT_StoNE,
  344.        DIAG_NEtoSW, BENT_WtoNE, ANGLE_NWtoNE,
  345.        (HOLE | HOLE_NORTHEAST) },
  346. /* W */  { CORNER_NORTHEAST, SHARP_EtoNE, 0, SHARP_EtoSE,
  347.        CORNER_SOUTHEAST, BENT_EtoSW, LINE_HORIZONTAL, BENT_EtoNW,
  348.        (HOLE | HOLE_EAST) },
  349. /* NW */ { BENT_NtoSE, ANGLE_NEtoSE, SHARP_EtoSE, 0, SHARP_StoSE,
  350.            ANGLE_SEtoSW, BENT_WtoSE, DIAG_SEtoNW,
  351.        (HOLE | HOLE_SOUTHEAST) }
  352.     };
  353.  
  354. void Retrace ( rr1, cc1, rr2, cc2, s )
  355.     /* work from target back to source, laying down the trace */
  356.     int rr1, cc1, rr2, cc2, s; /* start on side s */
  357.     {
  358.     int r0, c0, s0, r1, c1, s1, r2, c2, s2;
  359.     register int x, y;
  360.     long b;
  361.  
  362.     r1 = rr2;
  363.     c1 = cc2;
  364.     s1 = s;
  365.     r0 = c0 = s0 = ILLEGAL;
  366.     do {
  367.         /* find where we came from to get here */
  368.         switch (x = GetDir( r2 = r1, c2 = c1, s2 = s1 )) {
  369.         case FROM_NORTH:    r2++;        break;
  370.         case FROM_EAST:            c2++;    break;
  371.         case FROM_SOUTH:    r2--;        break;
  372.         case FROM_WEST:            c2--;    break;
  373.         case FROM_NORTHEAST:    r2++;    c2++;    break;
  374.         case FROM_SOUTHEAST:    r2--;    c2++;    break;
  375.         case FROM_SOUTHWEST:    r2--;    c2--;    break;
  376.         case FROM_NORTHWEST:    r2++;    c2--;    break;
  377.         case FROM_OTHERSIDE:    s2 = 1-s2;    break;
  378.         default:
  379.             fprintf( stderr, "internal error\n" );
  380.             exit( -1 );
  381.             break;
  382.             }
  383.         if (r0 != ILLEGAL)
  384.             y = GetDir( r0, c0, s0 );
  385.         /* see if target or hole */
  386.         if ((r1 == rr2 && c1 == cc2) || (s1 != s0)) {
  387.             switch (x) {
  388.             case FROM_NORTH:
  389.               OrCell( r1, c1, s1, HOLE_NORTH );  break;
  390.             case FROM_EAST:
  391.               OrCell( r1, c1, s1, HOLE_EAST );  break;
  392.             case FROM_SOUTH:
  393.               OrCell( r1, c1, s1, HOLE_SOUTH );  break;
  394.             case FROM_WEST:
  395.               OrCell( r1, c1, s1, HOLE_WEST );  break;
  396.             case FROM_NORTHEAST:
  397.               OrCell( r1, c1, s1, HOLE_NORTHEAST );  break;
  398.             case FROM_SOUTHEAST:
  399.               OrCell( r1, c1, s1, HOLE_SOUTHEAST );  break;
  400.             case FROM_SOUTHWEST:
  401.               OrCell( r1, c1, s1, HOLE_SOUTHWEST );  break;
  402.             case FROM_NORTHWEST:
  403.               OrCell( r1, c1, s1, HOLE_NORTHWEST );  break;
  404.             case FROM_OTHERSIDE:
  405.             default:
  406.                 fprintf( stderr, "internal error\n" );
  407.                 exit( -1 );
  408.                 break;
  409.                 }
  410.             }
  411.         else {
  412.             if ((y == FROM_NORTH
  413.                 || y == FROM_NORTHEAST
  414.                 || y == FROM_EAST
  415.                 || y == FROM_SOUTHEAST
  416.                 || y == FROM_SOUTH
  417.                 || y == FROM_SOUTHWEST
  418.                 || y == FROM_WEST
  419.                 || y == FROM_NORTHWEST)
  420.                 && (x == FROM_NORTH
  421.                 || x == FROM_NORTHEAST
  422.                 || x == FROM_EAST
  423.                 || x == FROM_SOUTHEAST
  424.                 || x == FROM_SOUTH
  425.                 || x == FROM_SOUTHWEST
  426.                 || x == FROM_WEST
  427.                 || x == FROM_NORTHWEST
  428.                 || x == FROM_OTHERSIDE)
  429.                 && (b = bit[y-1][x-1])) {
  430.                 OrCell( r1, c1, s1, b );
  431.                 if (b & HOLE)
  432.                     OrCell( r2, c2, s2, HOLE );
  433.                 }
  434.             else {
  435.                 fprintf( stderr, "internal error\n" );
  436.                 exit( -1 );
  437.                 }
  438.             }
  439.         if (r2 == rr1 && c2 == cc1) { /* see if source */
  440.             switch (x) {
  441.             case FROM_NORTH:
  442.               OrCell( r2, c2, s2, HOLE_SOUTH );  break;
  443.             case FROM_EAST:
  444.               OrCell( r2, c2, s2, HOLE_WEST );  break;
  445.             case FROM_SOUTH:
  446.               OrCell( r2, c2, s2, HOLE_NORTH );  break;
  447.             case FROM_WEST:
  448.               OrCell( r2, c2, s2, HOLE_EAST );  break;
  449.             case FROM_NORTHEAST:
  450.               OrCell( r2, c2, s2, HOLE_SOUTHWEST );  break;
  451.             case FROM_SOUTHEAST:
  452.               OrCell( r2, c2, s2, HOLE_NORTHWEST );  break;
  453.             case FROM_SOUTHWEST:
  454.               OrCell( r2, c2, s2, HOLE_NORTHEAST );  break;
  455.             case FROM_NORTHWEST:
  456.               OrCell( r2, c2, s2, HOLE_SOUTHEAST );  break;
  457.             case FROM_OTHERSIDE:
  458.             default:
  459.                 fprintf( stderr, "internal error\n" );
  460.                 exit( -1 );
  461.                 break;
  462.                 }
  463.             }
  464.         /* move to next cell */
  465.         r0 = r1; c0 = c1; s0 = s1;
  466.         r1 = r2; c1 = c2; s1 = s2;
  467.         } while (!(r2 == rr1 && c2 == cc1));
  468.     }
  469.  
  470. int GetApxDist ( r1, c1, r2, c2 ) /* calculate approximate distance */
  471.     int r1, c1, r2, c2;
  472.     {
  473.     register int d1, d2; /* row and column deltas */
  474.     int d0; /* temporary variable for swapping d1 and d2 */
  475.     /* NOTE: the -25 used below is because we are not going */
  476.     /* from the center of (r1,c1) to the center of (r2,c2), */
  477.     /* we are going from the edge of a hole at (r1,c1) to   */
  478.     /* the edge of a hole at (r2,c2). holes are 25 mils in  */
  479.     /* diameter (12.5 mils in radius), so we back off by 2  */
  480.     /* radii.                                               */
  481.     if ((d1 = r1-r2) < 0) /* get absolute row delta */
  482.         d1 = -d1;
  483.     if ((d2 = c1-c2) < 0) /* get absolute column delta */
  484.         d2 = -d2;
  485.     if (!d1) /* in same row? */
  486.         return( (d2*50)-25 ); /* 50 mils per cell */
  487.     if (!d2) /* in same column? */
  488.         return( (d1*50)-25 ); /* 50 mils per cell */
  489.     if (d1 > d2) { /* get smaller into d1 */
  490.         d0 = d1;
  491.         d1 = d2;
  492.         d2 = d0;
  493.         }
  494.     d2 -= d1; /* get non-diagonal part of approximate route */
  495.     return( (d1*71)+(d2*50)-25 ); /* 71 mils diagonally per cell */
  496.     }
  497. /* distance to go through a cell */
  498. static int dist[10][10] = { /* OT=Otherside, OR=Origin (source) cell */
  499.      /* N, NE,  E, SE,  S, SW,  W, NW,   OT, OR */
  500. /* N  */ { 50, 60, 35, 60, 99, 60, 35, 60,   12, 12 },
  501. /* NE */ { 60, 71, 60, 71, 60, 99, 60, 71,   23, 23 },
  502. /* E  */ { 35, 60, 50, 60, 35, 60, 99, 60,   12, 12 },
  503. /* SE */ { 60, 71, 60, 71, 60, 71, 60, 99,   23, 23 },
  504. /* S  */ { 99, 60, 35, 60, 50, 60, 35, 60,   12, 12 },
  505. /* SW */ { 60, 99, 60, 71, 60, 71, 60, 71,   23, 23 },
  506. /* W  */ { 35, 60, 99, 60, 35, 60, 50, 60,   12, 12 },
  507. /* NW */ { 60, 71, 60, 99, 60, 71, 60, 71,   23, 23 },
  508.  
  509. /* OT */ { 12, 23, 12, 23, 12, 23, 12, 23,   99, 99 },
  510. /* OR */ { 99, 99, 99, 99, 99, 99, 99, 99,   99, 99 }
  511.     };
  512.  
  513. /* distance around (circular) segment of hole */
  514. static int circ[10][10] = { /* OT=Otherside, OR=Origin (source) cell */
  515.      /* N, NE,  E, SE,  S, SW,  W, NW,   OT, OR */
  516. /* N  */ { 39, 29, 20, 10,  0, 10, 20, 29,   99, 0 },
  517. /* NE */ { 29, 39, 29, 20, 10,  0, 10, 20,   99, 0 },
  518. /* E  */ { 20, 29, 39, 29, 20, 10,  0, 10,   99, 0 },
  519. /* SE */ { 10, 20, 29, 39, 29, 20, 10,  0,   99, 0 },
  520. /* S  */ {  0, 10, 20, 29, 39, 29, 20, 10,   99, 0 },
  521. /* SW */ { 10,  0, 10, 20, 29, 39, 29, 20,   99, 0 },
  522. /* W  */ { 20, 10,  0, 10, 20, 29, 39, 29,   99, 0 },
  523. /* NW */ { 29, 20, 10,  0, 10, 20, 29, 39,   99, 0 },
  524.  
  525. /* OT */ { 99, 99, 99, 99, 99, 99, 99, 99,   99, 0 },
  526. /* OR */ { 99, 99, 99, 99, 99, 99, 99, 99,   99, 0 }
  527.     };
  528.  
  529. /* penalty for routing holes and turns, scaled by sharpness of turn */
  530. static int penalty[10][10] = { /* OT=Otherside, OR=Origin (source) cell */
  531.      /* N, NE,  E, SE,  S, SW,  W, NW,   OT, OR */
  532. /* N  */ {  0,  5, 10, 15, 20, 15, 10,  5,   50, 0 },
  533. /* NE */ {  5,  0,  5, 10, 15, 20, 15, 10,   50, 0 },
  534. /* E  */ { 10,  5,  0,  5, 10, 15, 20, 15,   50, 0 },
  535. /* SE */ { 15, 10,  5,  0,  5, 10, 15, 20,   50, 0 },
  536. /* S  */ { 20, 15, 10,  5,  0,  5, 10, 15,   50, 0 },
  537. /* SW */ { 15, 20, 15, 10,  5,  0,  5, 10,   50, 0 },
  538. /* W  */ { 10, 15, 20, 15, 10,  5,  0,  5,   50, 0 },
  539. /* NW */ {  5, 10, 15, 20, 15, 10,  5,  0,   50, 0 },
  540.  
  541. /* OT */ { 50, 50, 50, 50, 50, 50, 50, 50,  100, 0 },
  542. /* OR */ {  0,  0,  0,  0,  0,  0,  0,  0,    0, 0 }
  543.     };
  544.  
  545. /*
  546. ** x is the direction to enter the cell of interest.
  547. ** y is the direction to exit the cell of interest.
  548. ** z is the direction to really exit the cell, if y=FROM_OTHERSIDE.
  549. ** return the distance of the trace through the cell of interest.
  550. ** the calculation is driven by the tables above.
  551. */
  552.  
  553. int CalcDist ( x, y, z )
  554.     /* calculate distance of a trace through a cell */
  555.     int x, y, z;
  556.     {
  557.     int adjust;
  558.  
  559.     adjust = 0; /* set if hole is encountered */
  560.     if (x == EMPTY)
  561.         x = 10;
  562.     if (y == EMPTY)
  563.         y = 10;
  564.     else if (y == FROM_OTHERSIDE) {
  565.         if (z == EMPTY)
  566.             z = 10;
  567.         adjust = circ[x-1][z-1] + penalty[x-1][z-1];
  568.         }
  569.     return( dist[x-1][y-1] + penalty[x-1][y-1] + adjust );
  570.     }
  571.  
  572.  
  573.  
  574. Figure 1: Pseudo-code for the breadth-first search algorith
  575.  
  576. BFS Algorithm  (* breadth-first search *)
  577.    (* Search a graph or state space, depending on the problem definition. *)
  578.    (* S is the start node, T is the goal node. *)
  579.    (* Open is an ordered list of nodes (ordered by arrival time; nodes enter
  580.       at the tail and leave at the head), also called a queue. Closed is a set
  581.       of nodes (order doesn't matter). In general, nodes that need to be
  582.       searched are put on Open. As they are searched, they are removed from
  583.       Open and put in Closed. *)
  584.    (* Pred is defined for each node, and is a list of "came from" indications,
  585.       so when we finally reach T, we traverse Pred to construct a path to S. *)
  586. 1  Open <- {S}  (* a list of one element *)
  587.    Closed <- {}  (* the empty set *)
  588.    Pred[S] <- NULL,  found <- FALSE
  589.    WHILE Open <> {} and not found DO
  590. 5     x <- the first node on Open
  591.       Open <- Open - {x}  (* remove x from Open *)
  592.       Closed <- Closed + {x}  (* put x in Closed *)
  593.       IF x = T THEN found <- TRUE  (* we're done *)
  594.       ELSE  (* continue search through node x *)
  595. 10       let R be the set of neighboring nodes of x
  596.          FOR each y in R DO
  597.             IF y is not on Open or in Closed THEN
  598.                Pred[y] <- x  (* remember where we came from *)
  599.                Open <- Open + {y}  (* put y on Open (at the tail) *)
  600. 15 IF found THEN
  601.       use Pred[T] to find Pred[Pred[T]] and so on until S is reached
  602.       (* this traces out the solution path in reverse *)
  603.    ELSE T cannot be reached from S
  604.  
  605.  
  606.  
  607. Figure 3: Pseudo-code for the A* algorithm  
  608.  
  609. A* Algorithm  (* heuristic search *)
  610.    (* Search a graph or state space, depending on the problem definition. *)
  611.    (* S is the start node, T is the goal node. *)
  612.    (* Open is an ordered list of nodes (ordered by lowest F value; see below),
  613.       also called a priority queue. Closed is a set of nodes (order doesn't
  614.       matter). In general, nodes that need to be searched are put on Open (at
  615.       the proper position). As they are searched, they are removed from Open
  616.       and put in Closed. Occasionally a newer, better route will be found to a
  617.       node after it has already been searched, in which case we remove it from
  618.       Closed and put it back on Open to be reconsidered. *)
  619.    (* G[x] is the distance already traveled to get from S to node x, and is
  620.       known exactly. H(x) is a function (heuristic) which returns an estimate
  621.       of the distance from node x to T. F[x] is the estimated distance from S
  622.       to T by going through node x, and is computed by F[x] = G[x] + H(x).
  623.       H(x) can be calculated for any node, but F[x] and G[x] only become
  624.       defined when node x is visited. *)
  625.    (* Pred is defined for each node, and is a list of "came from" indications,
  626.       so when we finally reach T, we traverse Pred to construct a path to
  627.       S. *)
  628.    (* Distance(x,y) is a function for calculating the distance between two
  629.       neighboring nodes. *)
  630. 1  Open <- {S}  (* a list of one element *)
  631.    Closed <- {}  (* the empty set *)
  632.    G[S] <- 0,  F[S] <- 0,  Pred[S] <- NULL,  found <- FALSE
  633.    WHILE Open <> {} and not found DO
  634. 5     x <- the first node on Open  (* node with smallest F value *)
  635.       Open <- Open - {x}  (* remove x from Open *)
  636.       Closed <- Closed + {x}  (* put x in Closed *)
  637.       IF x = T THEN found <- TRUE  (* we're done *)
  638.       ELSE  (* continue search through node x *)
  639. 10       let R be the set of neighboring nodes of x
  640.          FOR each y in R DO
  641.             IF y is not on Open or in Closed THEN
  642.                G[y] <- G[x] + Distance(x,y)
  643.                F[y] <- G[y] + H(y)  (* estimate solution path length *)
  644. 15             Pred[y] <- x  (* remember where we came from *)
  645.                Open <- Open + {y}  (* put y on Open *)
  646.             ELSE  (* y is on Open or in Closed *)
  647.                IF (G[x] + Distance(x,y)) < G[y] THEN
  648.                   (* we've found a better route to y *)
  649. 20                G[y] <- G[x] + Distance(x,y)
  650.                   F[y] <- G[y] + H(y)
  651.                   Pred[y] <- x  (* remember where we came from *)
  652.                   IF y is on Open THEN
  653.                      reposition y according to F[y]
  654. 25                ELSE  (* y is in Closed *)
  655.                      Closed <- Closed - {y}  (* remove y from Closed *)
  656.                      Open <- Open + {y}  (* put y on Open *)
  657.    IF found THEN
  658.       use Pred[T] to find Pred[Pred[T]] and so on until S is reached
  659. 30    (* this traces out the solution path in reverse *)
  660.    ELSE T cannot be reached from S
  661.  
  662.  
  663.  
  664.